﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Assets.Scripts.Algrithm
{
    public class MinHeap<T> where T : IComparable<T>
    {
        private readonly List<T> _heap;

        public MinHeap()
        {
            _heap = new List<T>();
        }

        public void Insert(T item)
        {
            _heap.Add(item);
            int curIdx = _heap.Count - 1;
            while (curIdx > 0)
            {
                int parentIdx = (curIdx - 1) / 2;
                if (_heap[curIdx].CompareTo(_heap[parentIdx]) < 0)
                {
                    Swap(curIdx, parentIdx);
                    curIdx = parentIdx;
                }
                else
                {
                    break;
                }
            }
        }

        /// <summary>
        /// 从指定节点堆化（使堆满足小顶结构）
        /// !! 但是只考虑了从这个点向下堆化，未考虑到向上堆化
        /// </summary>
        public void MinHeapify(int index)
        {
            //假设当前元素就是(以 index 为顶的子树的)最小元素
            int minimum = index;
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;
            //从index leftChild 和 rightChild 中找出最小元素
            if (leftChild < _heap.Count && _heap[index].CompareTo(_heap[index]) > 0)
            {
                minimum = leftChild;
            }

            if (rightChild < _heap.Count && _heap[index].CompareTo(_heap[index]) > 0)
            {
                minimum = rightChild;
            }

            if (minimum != index)
            {
                //将最小元素放到 index, 并从交换位继续向下整理
                Swap(minimum, index);
                MinHeapify(minimum);
            }
        }

        public T ExtractMin()
        {
            T min = _heap[0];
            _heap[0] = _heap[_heap.Count - 1];
            _heap.RemoveAt(_heap.Count - 1);
            MinHeapify(0);
            return min;
        }


        public void Swap(int i, int j) => (_heap[i], _heap[j]) = (_heap[j], _heap[i]);
        public T[] ToArray()
        {
            return _heap.ToArray();
        }
    }
}
